package cg.studio.algorithm;

public class HeapUtil
{
  public static int parent( int i )
  {
    return (i-1)/2;
  }
  
  public static int left( int i )
  {
    return i+i+1;
  }

  public static int right( int i )
  {
    return i+i+2;
  }
  
  public static void maxHeapify( int[] values, int rootIndex )
  {
    maxHeapify( values, values.length, rootIndex );
  }

  public static void maxHeapify( int[] values, int size, int rootIndex )
  {
    int left = left( rootIndex );
    int right = right( rootIndex );
    int largestValueIndex = rootIndex;
    if( left < size && values[left] > values[ largestValueIndex ] )
    {
      largestValueIndex = left;
    }
    if( right < size && values[right] > values[ largestValueIndex ] )
    {
      largestValueIndex = right;
    }
    
    if( largestValueIndex == rootIndex )
      return;
    
    //swap
    int tmp = values[rootIndex];
    values[rootIndex] = values[largestValueIndex];
    values[largestValueIndex] = tmp;
    
    //maxHeapify sub tree
    maxHeapify( values, size, largestValueIndex );
  }
  
  /**
   * from last parent node to the root, maxHeapify
   * @param values
   */
  public static void buildMaxHeap( int[] values )
  {
    int lastParent = parent( values.length-1 );
    for( int i=lastParent; i>=0; --i )
    {
      maxHeapify( values, i );
    }
  }
}
